#include<stdio.h>
#include<stdlib.h>
#include "dsstring.h"

int r_strlen(const char* str) {
    int res = 0;
    while(str[res]) ++res;
    return res;
}

int r_strfind(const char* str, const char* pattern, int len1, int len2) {
    for(int i=0;i<=len1 - len2;i++) {
        int res = 1;
        for(int j=0;j<len2;j++) res &= str[i+j] == pattern[j];
        if(res) return i;
    }
    return -1;
}

void r_strrep(char *str, int maxlen, const char* src, const char* dst, int* cnt, int lenstr, int lensrc, int lendst) {
    if(lenstr - lensrc + lendst >= maxlen) return;
    int pos = r_strfind(str, src, lenstr, lensrc);
    if(pos == -1) return;
    if(lensrc > lendst) 
        for(int i=pos;i<=lenstr - lensrc + lendst;i++) str[i] = str[i + lensrc - lendst];
    else 
        for(int i=lenstr;i>pos;i--) str[i + lendst - lensrc] = str[i];
    for(int i=0;i<lendst;i++) str[pos + i] = dst[i];
    ++*cnt;
    r_strrep(str, maxlen, src, dst, cnt, lenstr + lendst - lensrc, lensrc, lendst); 
}

int str_replace(const char *in, char *out, int outlen, const char *oldstr, const char *newstr){
    int len = r_strlen(in), ans = 0;
    if(len >= outlen) return 0;
    for(int i=0;i<=len;i++) out[i] = in[i];
    r_strrep(out, outlen, oldstr, newstr, &ans, len, r_strlen(oldstr), r_strlen(newstr));
    return ans;
}

// -------------------------
// TEST

char res[5000];
char str[5000], src[5000], dst[5000];

int main() {
    int outlen;
    scanf("%s %d %s %s", str, &outlen, src, dst);
    int ans = str_replace(str, res, outlen, src, dst);
    printf("%d\n%s", ans, res);
}